package main

import (
	"fmt"
)

func main() {
	height := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
	//height := []int{1, 1}
	area := maxArea(height)
	fmt.Println(area)
}

//11. 盛最多水的容器
//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//
//返回容器可以储存的最大水量。
//
//说明：你不能倾斜容器。

// 输入：[1,8,6,2,5,4,8,3,7]
// 输出：49
// 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
// 示例 2：
//
// 输入：height = [1,1]
// 输出：1

// 超时
func maxArea1(height []int) int {
	area := 0
	// 遍历求面积
	count := len(height)

	if count == 1 {
		return 0
	}
	for i := 0; i < count; i++ {

		for j := 1; j < count; j++ {
			// 取两者小的值
			h := height[i]
			if height[i] > height[j] {
				h = height[j]
			}
			tmp := (j - i) * h
			if tmp > area {
				area = tmp
			}
		}
	}

	return area
}

// 超时
func maxArea2(height []int) int {
	area := 0
	// 遍历求面积
	count := len(height)

	if count == 1 {
		return 0
	}
	for i := 0; i < count; i++ {
		for j := count - 1; j > i; j-- {
			// 取两者小的值
			h := height[i]
			if height[i] > height[j] {
				h = height[j]
			}
			tmp := (j - i) * h
			if tmp > area {
				area = tmp
			}
		}
	}

	return area
}

func maxArea(height []int) int {
	area := 0
	if len(height) == 1 {
		return 0
	}
	i := 0
	j := len(height) - 1
	for i < j {
		// 取两者小的值
		h := height[i]
		if height[i] > height[j] {
			h = height[j]
		}
		// 计算
		if (j-i)*h > area {
			area = (j - i) * h
		}
		// 移动位置
		if height[i] > height[j] {
			j--
		} else {
			i++
		}
	}

	return area
}
